\section{Heur\'istica Golosa}

\subsection{Presentaci\'on del problema}

Una heur\'istica es un algoritmo cuyo objetivo es ser pr\'actico y \'agil para resolver problemas, aunque no garantiza siempre la respuesta \'optima. Una heur\'istica golosa es aquella que se rige por un algoritmo goloso. En cada paso se elige la mejor alternativa con respecto a algo, sin considerar (o haci\'endolo d\'ebilmente) las implicancias de esta selecci\'on.
En general estos algoritmos nos permiten construir soluciones razonables, pero sub-\'optimas.

\subsection{Resoluci\'on}
Para la soluci\'on de este problema, mantenemos la entrada que ten\'iamos para el algoritmo exacto. La entrada constante $G K$ \textit{origen} y \textit{destino} y la din\'amica $M e s$ y $S$.

Al comenzar el algoritmo, $M$ est\'a vacia, $e$ es el \textit{origen}, $s$ es 0 y $S$ esta vacia.

En la primera iteraci\'on en el primer \textit{for} lleno la primer columna de $M$ analizando los adyacentes al origen, si $w_1$ es menor que $K$ agrego la informaci\'on correspondiente a la matriz y tambi\'en agrego el eje a $S$.
Luego de la primer iteraci\'on, cada vez que llamo a este \textit{for}, se decide si se actualiza la informaci\'on de cada nodo, es decir, si encuentro un camino con mejor $w_2$ y que sigue cumpliendo la cota $K$, entonces reescribo la posici\'on en $M$ para ese nodo en el $s$ correspondiente.

Luego de este \textit{for}, en vez de fijarnos en todos los posibles caminos que exiten, elegimos el que tiene mejor $w_2$, y a partir de este hacemos la recursi\'on aumentando el nivel en el \'arbol de backtracking $(s)$.

As\'i hasta agotar los ejes que cumplen la cota o hasta visitar todos los nodos.

Luego recontruyo el camino utilizando $M$

\subsection{Pseudoc\'odigo}

\begin{verbatim}
calcularCamino (Grafo G, Matriz M, List$<$Ejes$>$ S,
                 int s, int e, int K, int origen, int destino)
   for G->nodos
      if (existe EJE(e,d) en G)
         if (s==0 y W1 < K) //es la primera iteración?
            -Agrego Información a S
            -Actualizo la Matriz M asignandole de donde vengo
            y el costo de W1 y W2 al momento.
            CONTINUE //sigo a la siguiente iteración
         else
            if (s > 0)
               if (W1 de M hasta ahora + EJE(e,d).W1 no supera K)
                  -Agrego Información a S
                  -Si tengo un nuevo valor para el W2 al momento delnodo d,
                  o mejoro el W2 hasta ahora, agrego la info a M en el paso s
                  CONTINUE
                endif
            endif
         endif
      endif
      -Copio toda la información no actualizada de M a la columna s
   endfor
   Ordeno(S)
   if (S > 0 && s < G->cantNodos)
      g = Primero(S) //g es un eje
      EliminoPrimero(S)
      if (existe nodo no visitado en g)
	      g->v //tomo el nodo que todavía no visite de g
	      r = CalcularCamino(G,M,S,s+1,g->v, K, origen, destino)
	  endif
   endif
   if (recorri todos los nodos y hay camino a destino)
      -reconstruyo camino de origen a destino usando M
      return r
   else
      return NULL
   endif
endCalcularCamino
\end{verbatim}

\subsection{An\'alisis de complejidad}
Las asignaciones de variables a las estructuras din\'amicas $M$ y $S$ las hacemos en $O(1)$, ya que para meter y obtener en una matriz espec\'ifico la posici\'on y en la lista $S$ agrego siempre atras.

En cada paso del algoritmo me posiciono en un nodo distinto (comienzo en el origen) y luego en el \textit{IF} posterior al \textit{for} cambio a otro nodo y as\'i hasta que revise todos los nodos o se acaben las aristas que cumplan las condiciones pedidas, es decir la suma de $w_1 < K$. En cada nodo analizo todos sus posibles ejes que ser\'ian la cantidad de nodos en el grafo, entonces si $n$ es la cantidad de nodos de G, el algoritmo har\'ia $O(n)$ operaciones $O(n)$.
Ademas, cuando termino el \textit{for} donde se llena la matriz $M$, ordeno la lista $S$ para tener los ejes ordenados por $w_2$ que sirve para minimizar dicho costo, esto lo hago en $O(nlog(n))$.
Por \'ultimo reconstruir el camino una vez que finalizo la recursi\'on cuesta $O(n)$, ya que ingreso a la matriz $M$ en $O(1)$ y las operaciones siguientes tambi\'en son $O(1)$.

Entonces el algoritmo estar\'ia haciendo $O(n)*(O(m)+O(mlog(m)) + O(n)$ operaciones que es lo m\'ismo que $O(n^3log(n^3))$ porque el peor caso es el grafo completo.


\subsection{Experimentacion}
La experimentación se realizó en base a grafos armados de manera random, los mismos se crearon mediante un script en python que se encuentra dentro de la carpeta ” src” llamado generador.py . se generaron 500 instancias con nodos que se elegían de manera random entre 5 y 200, en base a la cantidad de nodos se generó el grafo completo y se tomó 3/4 de las aristas para que no sea el grafo completo ya que si todos los nodos eran adyacentes entre si y no servía tener todos los casos así. Los valores w1 y w2 de las aristas son números random entre 1 y 100 , el valor de k se genera al final luego de sumar todas los valores de w1 de las aristas saco el promedio y lo multiplico por un valor estimado por distancia entre nodos suponiendo que los nodos están mas próximos si la numeración es próxima.

\includegraphics[scale=0.8]{golosa.jpg} \\
Comparamos con un algoritmo de complejidad \Ode{n^3*log(n^2)} lo comparamos con una polinomial $n^3$ para comparar que es mayor a esta, como se puede observar en el grafico.


\subsection{C\'odigo de fuente}
\begin{verbatim}
Result* CalcularCaminoDijkstraGreedy(Graph* G,Graph* M, list<Edge*>* S,
                             int s,int e,int K,int origen,int destino){

   list<Edge*>* localS = new list<Edge*>;
   *localS = *S;
   Edge *f,*g,*h,*y;
   Result* r = NULL;
   M->nodesOrder.push_back(e);

   for (int d=0; d < G->nodes; d++){
      removeEdge(M,d,s);
      f = getEdge(G,e,d,1);
      if (d != e && f != NULL && f->id != -1 &&  !existNode(M,d) ){

          if(s==0 and f->w1 < K){
            g = createEdge(e,f->w1,f->w2);
            localS->push_back(f);
            putEdge(M,d,s,g);
            continue;
          }else{

             if( s > 0 ){
                g = getEdge(M,e,s-1);
                 if ( g!= NULL && g->w1 + f->w1 < K){
                    localS->push_back(f);
                    h = getEdge(M,d,s-1);
                    if ( h == NULL ||   g->w2 + f->w2 < h->w2 ||
                       ( g->w2+f->w2 == h->w2 &&  g->w1+f->w1 < h->w1 )){
                          y = createEdge(e , g->w1+f->w1, g->w2+f->w2);
                          putEdge(M,d,s,y);
                          continue;
                  }
                }
             }
          }

      }
      if (s > 0 ){
         g = getEdge(M,d,s-1);
         if (g != NULL){
            putEdge(M,d,s,g);
         }
      }
   }

   localS->sort(compareEdgesByW2);
   if (localS->size() > 0 && s < G->nodes){
      g = localS->front();
      localS->pop_front();
      if ( !existNode(M,g->u)){
         return  CalcularCaminoDijkstraGreedy(G,M,localS,s+1,g->u, K,origen, destino);
      }
      if (!existNode(M,g->v)){
            return  CalcularCaminoDijkstraGreedy(G,M,localS,s+1,g->v, K, origen,destino);
      }
   }

   s = min(s,G->nodes-1);
   g = getEdge(M,destino,s);
   if (g != NULL && g->id != -1){
      r = new Result;
      r->w1 = g->w1;
      r->w2 = g->w2;
      r->k = K;
      int p = destino;

      r->C.push_front(destino);
      while ( p != origen){

         if (g->id == origen ) break;
         r->C.push_front(g->id);
         //printf("inserto %d \n",g->id);
         g = getEdge(M,g->id,s);
         if (g == NULL){
            break;
         }

         p = g->id;
      }


      r->C.push_front(origen);
      return r;
   }
   return NULL;
}
\end{verbatim}
